#include <stdio.h>
//引入bool类型
#include <stdbool.h>
//此库包含malloc函数
#include <stdlib.h>

typedef struct LNode {
    int val;
    struct LNode *Next;
} LNode, *LinkList;
 


LinkList mergeTwoLists(LinkList l1, LinkList l2){
    //首先判断两个链表是否为空
    if(!l1&&!l2){
        //都为空，返回NULL
        return NULL;
    }else if(!l1||!l2){
        //有一个不为空，返回不为空的
        return l1?l1:l2;
    }else{
        //l1的第一个元素结点
        LinkList p1 = l1->Next;
        //l2的第一个元素结点
        LinkList p2 = l2->Next;
        int one1 = p1->val;
        int one2 = p2->val;
        //将l2插入l1
        if(one1 >= one2){
            //将one2插到one1前面  l1:头结点->one2->one1
            p2->Next = p1;
            l1->Next = p2;
        }else{
            //将one2查到one1后面  l1:头结点->one1->one2
            p1->Next = p2;
            l1->Next = p1;
        }
    }            
        
        LinkList head = (LinkList)malloc(sizeof(struct LNode));
        LinkList h=head;
        while(l1&&l2)
        {
            if(l1->val<=l2->val)
            {
                h->Next=l1;
                h=h->Next;
                l1=l1->Next;
            }
            else
            {
                h->Next=l2;
                h=h->Next;
                l2=l2->Next;
            }
        }
        h->Next=l1?l1:l2;
        LinkList H=head->Next;
        head->Next=NULL;
        free(head);
        return H;

}